package leetcode100;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }
}

class Tree {
    TreeNode root;

    public Tree() {
        Scanner sc = new Scanner(System.in);
        this.root = createTree(sc);
    }

    public Tree(TreeNode root) {
        this.root = root;
    }

    public TreeNode createTree(Scanner sc) {
        int value = sc.nextInt();
        if (value < 0) return null;

        TreeNode node = new TreeNode(value);
        node.left = this.createTree(sc);
        node.right = this.createTree(sc);
        return node;
    }

    public TreeNode getNode(int value) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(this.root);
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (node.val == value) return node;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);

        }
        return null;
    }

    public void visit() {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(this.root);
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        System.out.println();
    }
}

public class lc004 {

    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.visit();
        TreeNode node1 = tree.getNode(3);
        TreeNode node2 = tree.getNode(5);
        TreeNode node = lowestCommonAncestor(tree.root, node1, node2);
        System.out.println(node.val);
    }





    public static HashMap<TreeNode, TreeNode> parentTree(TreeNode root) {
        HashMap<TreeNode, TreeNode> map = new HashMap<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode node = null;
        map.put(root, root);
        queue.add(root);
        while (!queue.isEmpty()) {
            node = queue.poll();


            if (node.left != null) {
                map.put(node.left, node);
                queue.add(node.left);

            }
            if (node.right != null) {
                map.put(node.right, node);
                queue.add(node.right);

            }
        }

        return map;
    }


    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /*
            HashMap< 当前结点 , 父节点 >
         */
        HashMap<TreeNode, TreeNode> map = parentTree(root);
        HashSet<TreeNode> set = new HashSet<>();
        TreeNode node = p;
        int countP = 0;
        int countQ = 0;
        node = p;
        while (node != root) {
            countP++;
            node = map.get(node);
        }

        node = q;
        while (node != root) {
            countQ++;
            node = map.get(node);
        }

        TreeNode nodeP = null;
        TreeNode nodeQ = null;
        if (countP > countQ) {
            nodeP = p;
            nodeQ = q;
            for (int i = 0; i < countP - countQ; i++) {
                nodeP = map.get(nodeP);
            }
        } else {
            nodeQ = q;
            nodeP = p;
            for (int i = 0; i < countQ - countP; i++) {
                nodeQ = map.get(nodeQ);
            }
        }

        while (nodeQ != root) {
            if (nodeQ == nodeP) return nodeQ;
            nodeQ = map.get(nodeQ);
            nodeP = map.get(nodeP);
        }


        return root;
    }
}
